package math;

/**
 * 一开始在0位置，每次都可以向左或者向右边跳
 * 每次跳i步，
 *
 * @author Liaorun
 */
public class JumpToTargets {

    public static int reachNumber(long target) {
        if (target == 0) {
            return 0;
        }
        target = Math.abs(target);

        long l = 0;
        long r = target;
        long m;
        // 跳了几步
        long near = 0;
        while (l <= r) {
            m = (l + r) / 2;
            if (sum(m) >= target) {
                near = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        if (sum(near) == target) {
            // 跳到了目标位置，直接退出
            return (int) near;
        }

        if (((sum(near) - target) & 1) == 1) {
            near++;
        }

        if (((sum(near) - target) & 1) == 1) {
            near++;
        }

        return (int) near;
    }

    /**
     * 等差数列求和公式
     *
     * @param n 最后一项是数字几
     * @return
     */
    private static long sum(long n) {
        return (n * (n + 1)) / 2;
    }
}
